package class03


/*
	背包容量为w
	一共有 n 袋零食，低i袋零食体积为v[i] > 0
	总体不超过背包容量的情况下，
	一共有多少种零食装法？（总体积为0也算一种装法）
*/
func ways1(arr []int, w int) int {
	return process(arr, 0, w)
}

// 从左到右猜测模型
func process(arr []int, start, rest int) int {
	if rest < 0 {
		// 剩余容量小于0时，该可能性不存在
		return -1
	}
	if start == len(arr) {
		return 1
	}
	p1 := process(arr, start+1, rest)
	p2 := process(arr, start+1, rest-arr[start])
	if p2 != -1 {
		return p1 + p2
	} else {
		return p1
	}
}

func ways2(arr []int, w int) int {
	dp := make([][]int, len(arr)+1)
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, w+1)
	}
	for i:=0; i<=w; i++ {
		dp[len(arr)][i] = 1
	}
	for i:=0; i<len(arr); i++ {
		dp[i][0] = 1
	}
	for start:=len(arr)-1; start>=0; start-- {
		for rest:=1; rest<=w; rest++ {
			dp[start][rest] = dp[start+1][rest]
			if rest - arr[start] >= 0 {
				dp[start][rest] += dp[start+1][rest - arr[start]]
			}
		}
	}
	return dp[0][w]
}